package stackqueuemap;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Test2 {
    // 中缀表达式转后缀表达式
    // 思路：
    // 1.数字直接输出
    // 2.左括号入栈, 遇到右括号出栈直到左括号
    // 3.运算符比较优先级，将小于等于当前优先级的运算符出栈，大于的保留，最后当前运算符入栈
    // 4.最后将栈中元素全部出栈
    private static final Map<Character,Integer> priorityMap = new HashMap<>();
    static {
        priorityMap.put('+',1);
        priorityMap.put('-',1);
        priorityMap.put('*',2);
        priorityMap.put('/',2);
    }

    public static String prefixExprToPostfixExpr(String src) {
        StringBuilder res = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        int i = 0;
        while (i < src.length()) {
            char ch = src.charAt(i);
            if (Character.isDigit(ch)) {
                int val = 0;
                while (i < src.length() && Character.isDigit(src.charAt(i))) {
                    val = val*10 + Integer.parseInt(src.charAt(i)+"");
                    i ++;
                }
                res.append(val);
                continue;
            } else if (ch == '(') {
                stack.push('(');
            } else if (ch == ')') {
                while (stack.peek() != '(') {
                    res.append(stack.pop());
                }
                // 左括号也出栈
                stack.pop();
            } else {
                // 此时只能是运算符
                while (!stack.isEmpty() && stack.peek() != '(' && priorityMap.get(ch) <= priorityMap.get(stack.peek())) {
                    // 优先级不大于栈顶元素
                    res.append(stack.pop());
                }
                // 当前符号入栈
                stack.push(ch);
            }
            i ++;
        }
        // 栈内剩余符号出栈
        while (!stack.isEmpty()) {
            res.append(stack.pop());
        }
        return res.toString();
    }

    // 双栈求解中缀表达式求值
    public int solve (String s) {
        // write code here
        // 双栈：第一个栈用来存储数字
        //      第二个栈用来存储运算符
        Stack<Integer> nums = new Stack<>();
        Stack<Character> ops = new Stack<>();

        String src = s.replace(" ", "");
        int i = 0;
        while (i < src.length()) {
            char ch = src.charAt(i);
            if (Character.isDigit(ch)) {
                int val = 0;
                while (i < src.length() && Character.isDigit(src.charAt(i))) {
                    val = val * 10 + Integer.parseInt(src.charAt(i) + "");
                    i ++;
                }
                nums.push(val);
                continue;
            } else if (ch == '(') {
                ops.push('(');
            } else if (ch == ')') {
                while (ops.peek() != '(') {
                    cacl(nums, ops);
                }
                // 左括号也出栈
                ops.pop();
            } else {
                while (!ops.isEmpty() && ops.peek() != '(' && priorityMap.get(ch) <= priorityMap.get(ops.peek())) {
                    cacl(nums, ops);
                }
                ops.push(ch);
            }
            i ++;
        }
        while (!ops.isEmpty()) {
            cacl(nums,ops);
        }
        return nums.pop();
    }
    private void cacl(Stack<Integer> nums, Stack<Character> ops) {
        int val1 = nums.pop();
        int val2 = nums.pop();
        char sign = ops.pop();
        switch (sign) {
            case '+':
                nums.push(val1+val2);
                break;
            case '-':
                nums.push(val2-val1);
                break;
            case '*':
                nums.push(val1*val2);
                break;
        }
    }

    public static void main(String[] args) {
        String str = "9+(3-1)*3+10/2";
        String s = prefixExprToPostfixExpr(str);
        System.out.println(s);
    }
}
